import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-09-22
 * Time: 20:56
 */
public class Test {
    public static void main(String[] args) {
        int[] array1={1,6,2,4,89,31,24,67};
        int[] array2={2,5,4,3,7,6,11,8,9,10};
        //mergeSort1(array,0,array.length-1);
        //mergeSort2(array1);
        countSort(array2);
        System.out.println(Arrays.toString(array2));
    }
// 归并排序---递归
    public static void mergeSort1(int[] array, int left, int right){
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        mergeSort1(array,left,mid);
        mergeSort1(array,mid+1,right);

        merge(left,right,array);
    }
    public static void merge(int left,int right, int[] array){
        int mid=(left+right)/2;
        int i=left;
        int k=0;
        int j=mid+1;
        int[] tmp = new int[right-left+1];
        while(i<=mid && j<=right){
            if(array[i]<=array[j]){
                tmp[k]=array[i];
                i++;
                k++;
            }else{
                tmp[k]=array[j];
                k++;
                j++;
            }
        }
        while(i<=mid){
            tmp[k]=array[i];
            i++;
            k++;
        }
        while(j<=right){
            tmp[k]=array[j];
            k++;
            j++;
        }
        for (int p = 0; p < tmp.length; p++) {
            array[p+left] = tmp[p];
        }
    }

// 归并排序---非递归
    public static void mergeSort2(int[] array){
        int gap=1;
        while(gap<= array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left =i;
                int right=left+2*gap-1;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(left,right,array);
            }
            gap*=2;
        }
    }



// 计数排序
    public static void countSort(int[] array){
        int max=array[0];
        int min=array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i]>max){
                max=array[i];
            }
            if(array[i]<min){
                min=array[i];
            }
        }
        int len=max-min+1;
        int[] count=new int[len];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        int k=0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]!=0){
                array[k]=i+min;
                k++;
                count[i]--;
            }
        }
    }
}
